package leetcode.pre100;


import utils.TreeNode;

import java.util.Stack;

/**
 * @since 2019/12/5 0005 下午 8:17
 */
public class Code98_IsValidBST {


    private static Integer pre = null;
    public static boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
//        return doBST2(root);
        return doBST1(root);
    }
    public static boolean doBST1(TreeNode root){
        if(root == null) return true;
        boolean res = doBST1(root.left);
        if(!res) return false;
        if(pre != null && pre >= root.val) return false;
        pre = root.val;
        //assert res = true
        return doBST1(root.right);
    }
    //中序遍历应该有序
    public static boolean doBST2(TreeNode root){
        if(root == null){
            return true;
        }
        //注意这里用Long，因为root的val是Int类型，所以中序的第一个结点可能是Int.MIN。会出错
        Integer pre = null;
        int cur;
        Stack<TreeNode> stack = new Stack();
        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                cur = root.val;
                if(pre != null && cur <= pre) return false;
                pre = cur;
                root = root.right;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(isValidBST(root));
    }
}
